# there is a more concise DP solution

class Solution(object):
    def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: int
        """
        # slist = list(s)
        # while True:
        #     changed = False
        #     last = -1
        #     for i in range(len(slist)):
        #         if slist[i]=='0':
        #             continue
        #         if slist[i]==')' and last!=-1 and slist[last]=='(':
        #             slist[last]='0'
        #             slist[i]='0'
        #             changed=True
        #         last = i
        #     if not changed:
        #         break
        # n = 0
        # maxN = 0
        # for l in slist:
        #     if l=='0':
        #         n+=1
        #         maxN = max(maxN, n)
        #     else:
        #         n=0
        # return maxN

        dp = [0 for _ in range(len(s)+2)]
        for i in range(1, len(s)):
            if s[i]=='(':
                dp[i]=0
            elif s[i]==')' and s[i-1]=='(':
                dp[i]=dp[i-2]+2
            elif s[i]==')' and s[i-1]==')':
                front = i-1-dp[i-1]
                if front>=0 and s[front]=='(':
                    dp[i]=dp[front-1] + dp[i-1] + 2
                else:
                    dp[i]=0
        return max(dp)

print(Solution().longestValidParentheses("(()))())("))